package binary_search.leetcode_4_hard;

public class BinarySearch {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*
            由中位数的作用：将集合分成两个长度相等的子集，且其中一个子集的最小值 > 另一个子集的最大值
                由此可以通过 寻找分割线的方式来对数组进行划分，进行划分的条件就是上述中
                 https://app.yinxiang.com/shard/s57/nl/11178787/ddb2b1e6-e096-45d2-8277-407bca198d89/   1. 长度相等
                    2. 其中一个子集的最小值 > 另一个子集的最大值
                假设nums1 长度为 m， nums2长度为 n， 在 i ,j 位置处分别对两个数进行划分。

                若要保证条件1成立，则需要满足
                    当 m + n 为偶数时：i + j = m - i + n - j          j = (m + n) / 2 - i
                    当 m + n 为奇数时：i + j = m - i + n - j + 1      j = (m + n + 1) / 2 - i
                通过向上取整，将两式合并为   j = (m + n + 1) / 2 - i;  此时不论m + n和为奇或偶，不影响结果。

                由此公示可以看出，当m > n时， 将会导致 (m + n + 1) / 2 > i 进而导致 j 为负数
                    因此要保证nums1数组的为两者中长度较小者
         */
        if(nums1.length > nums2.length){
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;

        int totalLeft = (m + n + 1) / 2;

        //在[0,m]区间，寻找 i 位置，使得 nums1[i - 1] <= nums2[j] 且 nums2[j - 1] <= nums1[i]
        int left = 0;
        int right = m;
        while(left < right){
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;

            if(nums1[i - 1] > nums2[j]){
                //分割线应向左收缩[left, i - 1]
                right = i - 1;
            }else{
                //[i, right]
                left = i;
            }
        }
        //开始判断边界情况
        int i = left;
        int j = totalLeft - i;

        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if((m + n) % 2 == 0){
            //偶数
            return (double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }else{
            return Math.max(nums1LeftMax, nums2LeftMax);
        }
    }
}
